package com.example.algorithm.huawei_rongyao_29;

import java.util.*;

// 判断t1树中是否有与t2树拓扑结构完全相同的子树

/**
 * 标题：判断t1树中是否有与t2树拓扑结构完全相同的子树 | 时间限制：3秒 | 内存限制：262144K
 * 给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
 * 设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。
 * 输入描述:
 * 第一行输入两个整数 n 和 root，n 表示二叉树 t1 的总节点个数，root 表示二叉树 t1 的根节点。
 * 以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
 * 第 n+2 行输入两个整数 m 和 root，n 表示二叉树 t2 的总节点个数，root 表示二叉树 t2 的根节点。
 * 以下 m 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
 * 输出描述:
 * 如果 t1 树有与 t2 树拓扑结构完全相同的子树，则输出 "true"，否则输出 "false"。
 *
 *
 * 要判断 t1 树是否有与 t2 树拓扑结构完全相同的子树，可以采用递归的方法。
 * 首先，可以编写一个函数 isSameTree 来判断两个二叉树是否拥有相同的拓扑结构。该函数的基本逻辑是：
 * 如果两个树的根节点都为空，则它们相同，返回 true；
 * 如果其中一个树的根节点为空，另一个不为空，则它们不同，返回 false；
 * 如果两个树的根节点值不相同，则它们不同，返回 false；
 * 递归判断两个树的左子树和右子树是否相同。
 * 接下来，对于 t1 树的每一个节点，都调用 isSameTree 函数来判断以该节点为根的子树是否与 t2 树拓扑结构完全相同。
 * 这个程序首先读取输入的两棵二叉树，并构建对应的树结构。
 * 然后使用 hasSameSubtree 函数来判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
 * 在 hasSameSubtree 函数中，通过递归调用 isSameTree 函数来判断以每个节点为根的子树是否与 t2 树相同。
 *
 * 9 1
 *
 * 1 2 3
 * 2 4 5
 * 4 0 8
 * 8 0 0
 * 5 9 0
 * 9 0 0
 * 3 6 7
 * 6 0 0
 * 7 0 0
 *
 * 5 2
 *
 * 2 4 5
 * 4 0 8
 * 8 0 0
 * 5 9 0
 * 9 0 0
 *
 * 上例，实际测试过了，结果为true，与事实吻合，可以认为下面程序是对的。
 *
 * 9 1
 * 1 2 3
 * 2 4 5
 * 4 0 8
 * 8 0 0
 * 5 9 0
 * 9 0 0
 * 3 6 7
 * 6 0 0
 * 7 0 0
 * 5 2
 * 2 3 6
 * 3 0 7
 * 7 0 0
 * 6 8 0
 * 8 0 0
 * true
 *
 * 这个发觉实际测试时也是true。这个的t2树只是拓扑结构与t1中有一样的，但是节点上的值不是一样的。
 * 而本程序也判定为对。说明本程序其实只是判断结构，没有判定每个节点上的值。
 *
 *
 */
public class Q05_SameSubtree02 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取 t1 树的信息
        String inputLine1 = scanner.nextLine();
        int[] numbers1 = Utils.scannerAndTransIntoInt(inputLine1);
        int n1 = numbers1[0];
        int root1Val = numbers1[1];
        // 根据输入信息构件树。t2就是最终构建好的树
        TreeNode t1 = buildTree(scanner, n1, root1Val);

        // 读取 t2 树的信息
        String inputLine2 = scanner.nextLine();
        int[] numbers2 = Utils.scannerAndTransIntoInt(inputLine2);
        int n2 = numbers2[0];
        int root2Val = numbers2[1];
        // 根据输入信息构件树。t2就是最终构建好的树
        TreeNode t2 = buildTree(scanner, n2, root2Val);

        // 判断 t1 是否包含 t2 的拓扑子树
        boolean result = isSubtree(t1, t2);
        System.out.println(result ? "true" : "false");
    }

    // 根据输入构建二叉树
    public static TreeNode buildTree(Scanner scanner, int n, int rootVal) {

        // 根据输入信息构建树。t1就是最终构建好的树
        Map<Integer, int[]> nodes = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String inputLine = scanner.nextLine();
            int[] numbers = Utils.scannerAndTransIntoInt(inputLine);
            int fa = numbers[0];
            int lch = numbers[1];
            int rch = numbers[2];
            // map中以本轮int fa的值为键，然后以本轮int lch rch为装在一个数组里面为值。
            nodes.put(fa, new int[]{lch, rch});
        }
        // for 循环执行完之后，所有的fa都被装进去了。

        if (rootVal == 0) return null;
        TreeNode root = new TreeNode(rootVal);
        buildTreeHelper(root, nodes);
        return root;
    }


    private static void buildTreeHelper(TreeNode root, Map<Integer, int[]> nodes) {
        int[] children = nodes.get(root.val);
        if (children != null) {
            int left = children[0];
            int right = children[1];
            if (left != 0) {
                root.left = new TreeNode(left);
                buildTreeHelper(root.left, nodes);
            }
            if (right != 0) {
                root.right = new TreeNode(right);
                buildTreeHelper(root.right, nodes);
            }
        }
    }


    // 判断 t1 中是否有与 t2 拓扑结构相同的子树
    public static boolean isSubtree(TreeNode t1, TreeNode t2) {
        if (t1 == null) return false;
        // 在t1、t2级别先判断一波
        if (isSameTree(t1, t2)) return true;
        // 据我个人观察发现。如果这个方法这样放，那么，必须要t1树大于等于t2树。
        // 也就是t1树是比较大的树，t2树是比较小的树。
        // 所以，人家题目也说了，是判断t1树中是否有与t2树拓扑结构完全相同的子树
        // 非常明确，是t1中是否有t2。即使是t2包含了t1，那么，我们是不认为，t1中有t2的。
        // 所以，这里非常明确，是要看t1包不包含人家t2，所以，t1是那棵要不断拆解子树去和t2比的树。
        // 所以，这里固定就是isSubtree不断自己调用自己，每调用一轮就把t1左右字数都往下拆解一级。
        // 所以你看到，t1不断t1.left、t1.right这样拆了之后再给isSubtree方法。
        // isSubtree主要起拆解t1子树的作用。而isSameTree主要是判断当前级别的两个t1、t2是否结构一样。
        return isSubtree(t1.left, t2) || isSubtree(t1.right, t2);
    }


    // 检查两棵树是否拓扑结构相同
    public static boolean isSameTree(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
    }
}

